#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/**
 * 个人练习
 */
class Test{
private:
	TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){
		if(postorder.size() == 0) return NULL;
		// 1. 找到根的值
		int rootValue = postorder[postorder.size()-1];
		// 2. 建立根节点
		TreeNode* root = new TreeNode(rootValue);
		// 说明已经是根节点了，不需要切割了。
		if(postorder.size()==1){
			return root;
		}
		// 3. 在中序遍历中找到根对应的下标
		int rootIndex = 0;
		while(rootIndex < inorder.size()){
			if(inorder[rootIndex] == rootValue){
				break;	
			}
			rootIndex++;
		}
		// 4. 根据中序根的位置切割
		vector<int> leftInorder(inorder.begin(),inorder.begin()+rootIndex);
		vector<int> rightInorder(inorder.begin()+rootIndex+1,inorder.end());
		// 5. 根据左边中序的大小和右边中序的大小切割后序数组
		postorder.resize(postorder.size()-1);
		vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
		vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
		// 开启递归
		root->left = traversal(leftInorder,leftPostorder);
		root->right = traversal(rightInorder,rightPostorder);
		return root;
	}
public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		if(inorder.size()==0 || postorder.size() == 0) return NULL;
		return traversal(inorder,postorder);
	}
};

/**
 * 答案解析
 */
class Solution {
private:
	TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
		if (postorder.size() == 0) return NULL;
		
		// 后序遍历数组最后一个元素，就是当前的中间节点
		int rootValue = postorder[postorder.size() - 1];
		TreeNode* root = new TreeNode(rootValue);
		
		// 叶子节点
		if (postorder.size() == 1) return root;
		
		// 找到中序遍历的切割点
		int delimiterIndex;
		for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
			if (inorder[delimiterIndex] == rootValue) break;
		}
		
		// 切割中序数组
		// 左闭右开区间：[0, delimiterIndex)
		vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
		// [delimiterIndex + 1, end)
		vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
		
		// postorder 舍弃末尾元素
		postorder.resize(postorder.size() - 1);
		
		// 切割后序数组
		// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
		// [0, leftInorder.size)
		vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
		// [leftInorder.size(), end)
		vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
		
		root->left = traversal(leftInorder, leftPostorder);
		root->right = traversal(rightInorder, rightPostorder);
		
		return root;
	}
public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		if (inorder.size() == 0 || postorder.size() == 0) return NULL;
		return traversal(inorder, postorder);
	}
};

int main(){
	
}
